package com.github.yangyishe.p200;

import com.github.yangyishe.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 173. 二叉搜索树迭代器
 * https://leetcode.cn/problems/binary-search-tree-iterator/?envType=study-plan-v2&envId=top-interview-150
 * 实际就是在初始化项目的时候, 中序遍历把二叉树放在一个集合中
 *
 * 实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
 * BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
 * boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
 * int next()将指针向右移动，然后返回指针处的数字。
 * 注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
 *
 * 你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。
 *
 *
 *
 * 示例：
 *
 *
 * 输入
 * ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
 * [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
 * 输出
 * [null, 3, 7, true, 9, true, 15, true, 20, false]
 *
 * 解释
 * BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
 * bSTIterator.next();    // 返回 3
 * bSTIterator.next();    // 返回 7
 * bSTIterator.hasNext(); // 返回 True
 * bSTIterator.next();    // 返回 9
 * bSTIterator.hasNext(); // 返回 True
 * bSTIterator.next();    // 返回 15
 * bSTIterator.hasNext(); // 返回 True
 * bSTIterator.next();    // 返回 20
 * bSTIterator.hasNext(); // 返回 False
 *
 *
 * 提示：
 *
 * 树中节点的数目在范围 [1, 105] 内
 * 0 <= Node.val <= 106
 * 最多调用 105 次 hasNext 和 next 操作
 *
 *
 * 进阶：
 *
 * 你可以设计一个满足下述条件的解决方案吗？next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 O(h) 内存。其中 h 是树的高度。
 */
public class Problem173 {
    public static void main(String[] args) {
        Integer[] ints=new Integer[]{7, 3, 15, null, null, 9, 20};
        TreeNode treeNode = TreeNode.getInstanceNew(ints);

        BSTIterator bstIterator = new BSTIterator(treeNode);
        System.out.println(bstIterator.next());    // 返回 3
        System.out.println(bstIterator.next());    // 返回 7
        System.out.println(bstIterator.hasNext()); // 返回 True
        System.out.println(bstIterator.next());    // 返回 9
        System.out.println(bstIterator.hasNext()); // 返回 True
        System.out.println(bstIterator.next());    // 返回 15
        System.out.println(bstIterator.hasNext()); // 返回 True
        System.out.println(bstIterator.next());    // 返回 20
        System.out.println(bstIterator.hasNext()); // 返回 False

    }

}

class BSTIterator {

    LinkedList<TreeNode> nodeList=new LinkedList<>();

    public BSTIterator(TreeNode root) {
        midOrder(root);
    }

    public int next() {
        return nodeList.pop().val;
    }

    public boolean hasNext() {
        return nodeList.size()>0;
    }

    public void midOrder(TreeNode treeNode){
        if (treeNode.left!=null) {
            midOrder(treeNode.left);
        }

        nodeList.add(treeNode);

        if(treeNode.right!=null){
            midOrder(treeNode.right);
        }
    }
}

/**
 * 思路:
 * 实现其实跟是不是二叉树没有关系, 主要是将递归遍历的顺序隔开, 或者说, 记录当前位置
 *
 * 最简单粗暴的一种方法是初始化时, 就将所有元素存到一个数组中, 但这样不太优雅
 *
 * 原本我们使用中序遍历一颗二叉树, 是利用了递归. 递归中隐含使用了jvm栈.
 * 迭代器如果要实现, 就需要实现jvm栈的原理, 包含记录栈, 以及记录迭代位置
 *
 */
//class BSTIterator {
//
//    Stack<TreeNodeAndPosition> stack;
//    TreeNode root;
//
//    public BSTIterator(TreeNode root) {
//        this.stack=new Stack<>();
//        this.root=root;
//        stack.push(new TreeNodeAndPosition(root,'l'));
//    }
//
//
//    public int next() {
//        TreeNodeAndPosition current = stack.peek();
//        TreeNode currentNode = current.treeNode;
//        if(current.position =='l'){
//            if(currentNode.left!=null){
//                stack.push(new TreeNodeAndPosition(currentNode.left,'l'));
//                return next();
//            }else{
//                // do nothing. 表示左侧为空, 不需要遍历
//                current.position='m';
//                return next();
//            }
//        }else if(current.position=='m'){
//            current.position='r';
//            return currentNode.val;
//        }else if(current.position=='r'){
//            if(currentNode.right==null){
//                current.position='f';
//                return next();
//            }else{
//                // 表示右侧非空, 应当继续访问右侧的情况
//                stack.push(new TreeNodeAndPosition(currentNode.right,'l'));
//                return next();
//            }
//        }else{
//            // 表示右侧为空, 当前栈帧无用, 应当收回
//            stack.pop();
//            TreeNodeAndPosition peek = stack.peek();
//            if(peek.position=='l'){
//                peek.position='m';
//            }else{
//                peek.position='f';
//            }
//            return next();
//        }
//
//    }
//
//    public boolean hasNext() {
//        while((stack.peek().position=='r'&&stack.peek().treeNode.right==null)||stack.peek().position=='f'){
//            stack.pop();
//            if(stack.peek().position=='r'&&stack.peek().treeNode.right==null){
//                stack.peek().position='f';
//            }
//        }
//        return stack.size()!=0;
//    }
//
//    /**
//     * 通常的中序遍历
//     */
//    public void infixOrder(TreeNode node){
//        if(node.left!=null){
//            infixOrder(node.left);
//        }
//
//        System.out.println(node);
//
//        if(node.right!=null){
//            infixOrder(node.right);
//        }
//    }
//}
//
///**
// * 模拟jvm的栈帧. 记录每次的递归参数, 以及代码执行位置
// */
//class TreeNodeAndPosition{
//    TreeNode treeNode;
//    // 表示当前节点的应当遍历的位置. 左:l;中:m;右:r. 只有当遍历到中时, 才能打印一个数据. 如果当前节点已访问完, 则为f
//    // l->m->r=>f
//    char position;
//
//
//    public TreeNodeAndPosition(TreeNode treeNode, char position) {
//        this.treeNode = treeNode;
//        this.position = position;
//    }
//}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */
